package com.zjt;

import java.util.*;

/**
 * 图 & 最大影响力算法
 */
public class Graph {
    /**
     * 随机数生成器
     */
    static private final Random random = new Random();
    /**
     * 哈希表;
     * 键：节点ID;
     * 值：节点的引用;
     */
    private final Map<Integer, Node> nodes = new HashMap<>();

    /**
     * 从文件建图
     *
     * @param alluserlist 文件alluserlist.txt的路径
     * @param links       文件links.txt的路径
     */
    Graph(String alluserlist, String links) {
        List<String> nodes = MyFileReader.load(alluserlist);
        List<String> edges = MyFileReader.load(links);

        for (String s : nodes) {
            int id = Integer.parseInt(s);
            this.nodes.put(id, new Node(id));
        }

        for (String line : edges) {
            String[] quadruple = line.split(" ");

            int src = Integer.parseInt(quadruple[0]);
            int dts = Integer.parseInt(quadruple[1]);
            int dir = Integer.parseInt(quadruple[2]);
            double w = Double.parseDouble(quadruple[3]);

            Node n = this.nodes.get(src);
            n.addSuccessor(new Edge(
                    this.nodes.get(dts),
                    w,
                    dir
            ));
        }
    }

    /**
     * 生成随机数并检验是否能够激活下一个节点
     *
     * @param edge 待检验边
     * @return 是否能被激活
     */
    private static boolean threshold(Edge edge) {
        double threshold = edge.getWeight();
        return random.nextDouble() > threshold;
    }

    private static boolean isInactive(Node dts, Set<Node> positive, Set<Node> negative,
                                      Set<Node> archived, Set<Node> nextPositive, Set<Node> nextNegative) {
        return !archived.contains(dts) && !positive.contains(dts) && !negative.contains(dts)
                && !nextNegative.contains(dts) && !nextPositive.contains(dts);
    }

    /**
     * <b>注意:</b> 所有的参数在函数中不能被修改
     *
     * @param positive 被正激活的节点
     * @param negative 被负激活的节点
     * @param archived 之前被激活，现在已经失效的节点
     * @return 在本次模拟中可以激活的正节点的个数
     */
    private int virtualCascade(Set<Node> positive, Set<Node> negative, Set<Node> archived) {
        if (positive.isEmpty() && negative.isEmpty()) {
            return 0;
        }

        final Set<Node> nextPositive = new HashSet<>();
        final Set<Node> nextNegative = new HashSet<>();

        int rlt = 0;
        for (Node node : positive) {
            for (Edge edge : node.getSuccessors()) {
                Node dts = edge.getDts();
                if (isInactive(dts, positive, negative, archived, nextPositive, nextNegative)
                        && threshold(edge)) {
                    int direction = edge.getDirection();
                    if (direction == 1) //  positive influence
                    {
                        nextPositive.add(dts);
                        ++rlt;
                    } else {
                        nextNegative.add(dts);
                    }
                }
            }
        }

        for (Node node : negative) {
            for (Edge edge : node.getSuccessors()) {
                Node dts = edge.getDts();
                if (isInactive(dts, positive, negative, archived, nextPositive, nextNegative)
                        && threshold(edge)) {
                    int direction = edge.getDirection();
                    if (direction == -1)  // positive influence
                    {
                        nextPositive.add(dts);
                        ++rlt;
                    } else {
                        nextNegative.add(dts);
                    }
                }
            }
        }

        if (rlt == 0) {
            return rlt;
        }

        // nextArchived = union(positive, negative, archived)
        final Set<Node> nextArchived = new HashSet<>(archived);
        nextArchived.addAll(positive);
        nextArchived.addAll(negative);
        return rlt + virtualCascade(nextPositive, nextNegative, nextArchived);
    }

    /**
     * 以<i>seeds</i>为起始点执行<i>times</i>次<i>virtualCascade</i>
     *
     * @param positiveSeeds 起始被正向激活的节点集合
     * @param times 测试次数
     * @return 通过模拟估计的最大影响力
     */
    public double averageMaxInfluence(Set<Node> positiveSeeds, int times) {
        double rlt = 0;
        for (int i = 0; i < times; ++i) {
            rlt += virtualCascade(positiveSeeds, new HashSet<>(), new HashSet<>());
        }
        return rlt / times;
    }


    /**
     * 找到<I>k</I>为大小的最大影响力节点集合
     *
     * @param k     集合大小
     * @param times 估计最大影响力函数时的测试册数
     * @return <I>k</I>为大小的最大影响力节点集合
     */
    public Set<Node> bestPoints(int k, int times) {
        Set<Node> pickedNodes = new HashSet<>();

        for (int i = 0; i < k; ++i) {
            double maxSigma = 0;
            Node nodeToAdd = null;
            for (Node node : nodes.values()) // 对于每一个节点
            {
                if (!pickedNodes.contains(node)) // 如果未被选中
                {

                    Set<Node> pickedNodesAddOne = new HashSet<>(pickedNodes);
                    pickedNodesAddOne.add(node);

                    double newSigma = averageMaxInfluence(pickedNodesAddOne, times);
                    if (newSigma > maxSigma) {
                        maxSigma = newSigma;
                        nodeToAdd = node;
                    }
                }
            }
            System.out.println("no." + i + ", Influence = " + maxSigma);
            System.out.println("\t" + nodeToAdd);
            pickedNodes.add(nodeToAdd);
        }
        return pickedNodes;
    }
}
